package com.zs.letcode.illustration_of_algorithm;

import java.util.ArrayList;
import java.util.List;

/**
 * 剑指 Offer 57 - II. 和为 s 的连续正数序列
 * 输入一个正整数 target ，输出所有和为 target 的连续正整数序列（至少含有两个数）。
 * <p>
 * 序列内的数字由小到大排列，不同序列按照首个数字从小到大排列。
 * <p>
 * <p>
 * 示例 1：
 * <p>
 * 输入：target = 9
 * 输出：[[2,3,4],[4,5]]
 * 示例 2：
 * <p>
 * 输入：target = 15
 * 输出：[[1,2,3,4,5],[4,5,6],[7,8]]
 * <p>
 * 限制：
 * <p>
 * 1 <= target <= 10^5
 * <p>
 * 相关标签
 * 数学
 * 双指针
 * 枚举
 * <p>
 * 作者：Krahets
 * 链接：https://leetcode-cn.com/leetbook/read/illustration-of-algorithm/eufzm7/
 * 来源：力扣（LeetCode）
 * 著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。
 *
 * @author madison
 * @description
 * @date 2021/8/31 06:54
 */
public class Chapter71 {
    public static void main(String[] args) {

    }

    private class Solution {
        /**
         * 方法一：求和公式
         *
         * @param target
         * @return
         */
        public int[][] findContinuousSequence(int target) {
            int i = 1;
            double j = 2.0;
            List<int[]> res = new ArrayList<>();
            while (i < j) {
                j = (-1 + Math.sqrt(1 + 4 * (2 * target + (long) i * i - i))) / 2;
                if (j == (int) j) {
                    int[] ans = new int[(int) j - i + 1];
                    for (int k = i; k <= (int) j; k++)
                        ans[k - i] = k;
                    res.add(ans);
                }
                i++;
            }
            return res.toArray(new int[0][]);
        }

        /**
         * 方法二：滑动窗口（双指针）
         */
        public int[][] findContinuousSequence1(int target) {
            int i = 1, j = 2, s = 3;
            List<int[]> res = new ArrayList<>();
            while (i < j) {
                if (s == target) {
                    int[] ans = new int[j - i + 1];
                    for (int k = i; k <= j; k++) {
                        ans[k - i] = k;
                    }
                    res.add(ans);
                }
                if (s >= target) {
                    s -= i;
                    i++;
                } else {
                    j++;
                    s += j;
                }
            }
            return res.toArray(new int[0][]);
        }
    }
}
